class Solution {
  public:
    bool isMatch(string s, string p) {
        //添加空串
        s = " " + s;
        p = " " + p;
        int n = s.size();
        int m = p.size();
        vector<vector<bool>>dp(n, vector<bool>(m));//默认初始化为false
        dp[0][0] = true;//空串必定匹配设置true
        //原s串待匹配串，不可能和添加的空串匹配，i!=1,[i][0]默认为false
        for (int i = 0; i < n; i++) 
        {
            //如果原p串首字符为*有可能和添加的空串匹配，所以要从[0][1]开始匹配
            for (int j = 1; j < m; j++) 
            {
                if (p[j] != '*') {
                    dp[i][j] = i && j && dp[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?');
                } else {
                    dp[i][j] = (i && dp[i - 1][j]) || (j && dp[i][j - 1]);
                }

            }
        }
        return dp[n - 1][m - 1];
    }
};